/*
 * @lc app=leetcode id=97 lang=cpp
 *
 * [97] Interleaving String
 */
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {

        int l1 = s1.size();
        int l2 = s2.size();
        int len = s3.size();
        if (l1 + l2 != len) {
            return false;
        }

        vector<vector<bool>> memo(l1+1, vector<bool>(l2+1, false));
        memo[0][0] = true;

        for (int i=1; i<=l1; i++) {
            memo[i][0] = memo[i-1][0] && (s1[i-1] == s3[i-1]);
        }

        for (int i=1; i<=l2; i++) {
            memo[0][i] = memo[0][i-1] && (s2[i-1] == s3[i-1]);
        }

        for (int i=1; i<=l1; i++) {
            for (int j=1; j<=l2; j++) {
                memo[i][j] = (memo[i-1][j] && s1[i-1]==s3[i-1+j])  || 
                    (memo[i][j-1] && s2[j-1] == s3[i-1+j]);
            }
        }

        return memo[l1][l2];
    }
};

